package leetCode;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.List;


public class LeetCode_day1 {
	
	/**
	 * list is not sorted.
	 * Given an array of integers, find two numbers 
	 * such that they add up to a specific target number.
	 * Array.sort O(nlog(n))
	 * @param list
	 * @param target
	 * @return
	 */
	public static int[] twoSum(int[] list, int target){
		int[] result = new int[2];
		Arrays.sort(list);//nlogn
		int[] temp = null;
		for(int i = 0 ; i < list.length ; i++)
			if(list[i] > target) {
				temp = Arrays.copyOf(list, i);
				break;
			}
		if(temp == null) temp = list;
		
		result[0] = 0 ; result[1] = temp.length-1;
		while(result[0] < result[1] ){
			if(temp[result[0]] + temp[result[1]] != target){
				if(temp[result[0]] + temp[result[1]] > target) result[1]--;
				else if(temp[result[0]] + temp[result[1]] < target) result[0]++;
			}
			else return result;
		}
		if(result[0] >= result[1]) return null;
		return result;
	}
	
	public static double twoSortedMedian(int[] a , int[] b){
		int[] c = new int[a.length+b.length];
		int j = 0,k = 0;
		for(int i = 0 ; i < c.length ; i++){
			if(j < a.length && k < b.length)
				c[i] = a[j] < b[k]? a[j++] : b[k++];
			else if(j >= a.length) c[i] = b[k++];
			else c[i] = a[j++];
		}
		int m = c.length / 2;
		if(c.length % 2 == 1) return c[m];
		else return (c[m]+c[m-1])/2;
	}
	
	/**
	 * 
	 * 
	 * @param s
	 * @return
	 */
	public static String longestUnRepeatedSubString(String s){
		if(s == null || s.isEmpty()) return null;
		int maxLen = 1;
		String longestCandidate = s.substring(0, 1);
		//boolean[] flags = new boolean[256];
		HashMap<Character, Integer> cset = new HashMap<Character, Integer>();
		//iterate the string from character to character (start character of substring)
		for(int i = 0 ; i < s.length()-1 ; i++){//no need to go to the last character
			if(i+maxLen >= s.length()) break;
			cset.clear();
			boolean rflag = false;
			//add all characters of s.subString(i,maxLen) into cset
			//if there are repeated characters in this substring, continue
			for(int k = i ; k < i+maxLen ; k++){
				if(cset.containsKey(s.charAt(k))) {
					rflag = true; break;
				}else cset.put(s.charAt(k), k);
			}
			if(rflag) continue;
			//if there aren't repeated characters in substring(i,maxLen)
			//j means the end character of substring
			for(int j = i+maxLen ; j < s.length() ; j++){
				if(cset.containsKey((s.charAt(j)))){//j is repeated
					rflag = true;
					if(maxLen < j-i){
						maxLen = j-i;
						longestCandidate = s.substring(i,j);
					}else i = cset.get(s.charAt(j));
					//a repeated substring exists with a shorter length
					//let start character begins after the first repeated character 		
					break;
				}
			}
			if(!rflag){
				longestCandidate = s.substring(i);
				break;
			}
		}
		return longestCandidate;
	}
	/**
	 *
	 * Optimize the code.
	 * The original thought is viewing substrings as line segments 
	 * where two points are the same characters but this costs too much.
	 * 
	 * @param s
	 * @return
	 */
	//TODO
	public static String longestUnRepeatedSubString1(String s){
		if(s == null || s.isEmpty()) return null;
		int start = 0 , end = 2, maxLen= 1;
		HashMap<Character, Integer> map = new HashMap<Character, Integer>();
		map.put(s.charAt(0), 0);
		
		while(end <= s.length()){
			if(!map.containsKey(s.charAt(end-1))) map.put(s.charAt(end-1), end-1);
			else{
				if(maxLen < end - start - 1){
					maxLen = end - start - 1;
				}
			}
		}
		return null;
	}
	
	/**
	 * You are given two linked lists representing two non-negative numbers. 
	 * The digits are stored in reverse order and each of their nodes contain a single digit. 
	 * Add the two numbers and return it as a linked list.
	 * @param a
	 * @param b
	 * @return
	 */
	public static int[] addTwoNumbersLinkedList(int[] a , int[] b){
		//let a always be the longer one
		if(a.length < b.length){
			int[] longer = b;
			b = a; a = longer;
		}
		//int[] sum = new int[a.length < b.length ? b.length+1 : a.length+1];
		int[] sum = new int[a.length+1];
		int next = 0;
		for(int i = 0 ; i < b.length ; i++){
			int digitSum = a[i] + b[i] + next;
			sum[i] = digitSum - 10;
			next = digitSum / 10;
		}
		sum[b.length] = a[b.length] + next;
		for(int i = b.length+1 ; i< a.length ; i++) sum[i] = a[i]; 
		return sum;
	}
	/**
	 * Using suffix tree.
	 * O(m+n)
	 * @param s1
	 * @param s2
	 * @return
	 */
	public static String longestCommonSubstring1(String s1, String s2){
		String result = null;
		
		return result;
	}
	
	/**
	 * Dynamic programming.
	 * 
	 * if s1[i1,j1] is also a substring in s2, 
	 * then s1[i1-1,j1-1] is also a common substring.
	 * 
	 * Base case: s1[i1] is a common substring iff s1[i1] = s2[i2]
	 * Induction: 
	 * 			  s1[i1,j1] is a common substring iff
	 * 					s[i1,j1-1] is a common substring
	 * O(mn)
	 * @param s1
	 * @param s2
	 * @return
	 */
	public static String longestCommonSubstring2(String s1, String s2){
		if(s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0) return null;
		int maxLen = 0, end = 0;
		int[][] table = new int[s1.length()][s2.length()];
		
		for(int i = 0 ; i < s1.length() ; i++){
			for(int j = 0 ; j < s2.length() ; j++){
				if(s1.charAt(i) == s2.charAt(j)){
					if(i == 0 || j == 0){
						table[i][j] = 1;
					}else{
						table[i][j] = table[i-1][j-1] +1;
					}
					if(table[i][j] > maxLen){
						maxLen = table[i][j];
						end = i;
					}
				}
			}
		}
		return s1.substring(end-maxLen+1, end+1);
	}
	
	/**
	 * O(n) storage Dynamic Programming, only use two rows of the table
	 * O(mn)
	 * @param s1
	 * @param s2
	 * @return
	 */
	public static String longestCommonSubstring3(String s1, String s2){
		if(s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0) return null;
		int maxLen = 0, cost = 0, end = 0;
		int[] p = new int[s2.length()];
		int[] q = new int[s2.length()];
		
		for(int i = 0 ; i < s1.length() ; i++){
			for(int j = 0 ; j < s2.length() ; j++){
				if(s1.charAt(i) != s2.charAt(j)) cost = 0;
				else{
					if(i == 0 || j == 0) cost = 1;
					else cost = p[j-1] + 1;
				}
				q[j] = cost;
				if(cost > maxLen) {
					maxLen = cost;
					end = i;
				}
			}
			int[] swap = p;
			p = q;
			q = swap;
		}
		return s1.substring(end-maxLen+1, end+1);
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		LeetCode_day1.twoSum(new int[]{1,4,6,8,9,11,12,13}, 19);
		//System.out.println(LeetCode_day1.twoSortedMedian(new int[]{1,3,5},new int[]{2,6,8}));
		//System.out.println("asdf".substring(0, 4));
		System.out.println(longestUnRepeatedSubString("abcdeabcsecabcdef"));
		//int[] a = addTwoNumbersLinkedList(new int[]{1,2,0,3}, new int[]{3,2,5,7,4,3});
		//System.out.println(longestCommonSubstring3("abab","baba"));
	}

}
/**
 * Notice:
 * s.subString(0,1) means s[0]
 * s.subString(0,2) means s[0:1]
 * s.subString(a,b) means s[a:b-1], a + length = b
 * 
 * for(int i = 0 ; i < length ; i++){...}
 * i++ is the last command that be executed
 * 
 * HashMap is preferred (not synchronized and newer than Hashtable)
**/